# 一个支持迭代、排序、索引、切片等等(列表可以的它都可以)操作的链表(pop以后说，因为又有事情了，，，)

from copy import deepcopy


class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        
    def __str__(self):
        return str(self.val)
    
    def __eq__(self, obj):
        return self.val == obj.val if isinstance(obj, Node) else self.val == obj
    
    def __lt__(self, obj):
        return self.val < obj.val if type(obj) == isinstance(obj, Node) else self.val < obj
    
    def __next__(self):
        if self.iter:
            if self.curr:
                temp = self.curr
                self.curr = self.curr.next
                return temp
            self.iter = 0
            raise StopIteration
        else:
            self.iter = 1
            return self
    
    def __iter__(self):
        self.iter = 0
        self.curr = self
        return self.__next__()
    

class LinkNode:
    def __init__(self, node=None):
        self.head = node
    
    def __str__(self):
        if self.is_empty():
            return f"< class {__name__}.LinkNode: {[]}>"
        return f"< class {__name__}.LinkNode: {[i.val for i in self.head]}>"
    
    def __eq__(self, obj):
        if self.is_empty():
            return self.head == obj.head
        return list(self.head) == list(obj.head)
    
    def __it__(self, obj):
        if self.is_empty():
            return True
        return list(self.head) < list(obj.head)
    
    def __contains__(self, obj):
        if self.is_empty():
            return False
        for i in self.head:
            if obj == i:
                return True
        return False
    
    def __len__(self):
        if self.is_empty():
            return 0
        temp = 0
        for i in self.head:
            temp += 1
        return temp
    
    def __add__(self, obj):
        temp = deepcopy(self)
        for i in obj:
            temp.append(i, copy=True)
        return temp
    
    def __iter__(self):
        self.iter = 0
        self.curr = self.head
        return self
    
    def __next__(self):
        if self.iter:
            if self.curr:
                temp = self.curr
                self.curr = self.curr.next
                return temp
            else:
                self.iter = 0
                raise StopIteration
        else:
            self.iter = 1
            return self.__next__()
            
    def __getitem__(self, item):
        if isinstance(item, slice):
            res = LinkNode()
            temp = list(self)
            if not item.step:
                if item.start and item.stop:
                    step = 1 if item.start <= item.stop else -1
                else:
                    step = 1
            else:
                step = item.step
            if step > 0:
                if not item.start:
                    start = 0
                else:
                    start = max(item.start,0)
                if not item.stop:
                    end = len(self)
                else:
                    end = min(item.stop,len(self))
            else:
                if not item.start:
                    start = len(self)-1
                else:
                    start = min(item.start,len(self)-1)
                if not item.stop:
                    end = -1
                else:
                    end = max(item.stop,-1)
            for i in range(start,end,step):
                res.append(temp[i], copy=True)
            return res
        if item >= len(self) or item < -len(self):
            raise IndexError("linkNode index out of range")
        if item < 0:
            item = len(self)+item
        temp = self.head
        for i in range(1, item):
            temp = temp.next
        return temp
        
    def __setitem__(self, item, val):
        self.__getitem__(item).val = val
    
    def is_empty(self):
        return not bool(self.head)
    
    def insert(self, index, obj, copy=False):
        if copy:
            obj = deepcopy(obj)
        if not isinstance(obj, Node):
            obj = Node(obj)
        obj.next = None
        if not index:
            temp = self.head
            self.head = obj
            obj.next = temp
        else:
            if index < 0:
                index = len(self) + index
            if self.is_empty() or index >= len(self):
                self.append(obj)
            elif index < 0:
                self.insert(0, obj)
            else:
                temp = self.head
                curr = 1
                while curr < index:
                    temp = temp.next
                    curr += 1
                temp.next, obj.next = obj, temp.next
    
    def append(self, obj, copy=False):
        if copy:
            obj = deepcopy(obj)
        if not isinstance(obj, Node):
            obj = Node(obj)
        obj.next = None
        if self.is_empty():
            self.head = obj
        else:
            temp = self.head
            while temp.next:
                temp = temp.next
            temp.next = obj
    
    def remove(self, val):
        if self.is_empty():
            raise ValueError('LinkNode.remove(val): val not in LinkNode')
        temp = self.head
        if temp.val == val:
            self.head = temp.next
            del temp
        else:
            while temp.next:
                if temp.next.val ==  val:
                    del_item = temp.next
                    temp.next = temp.next.next
                    del del_item
                    return
                temp = temp.next
            else:
                raise ValueError('LinkNode.remove(val): val not in LinkNode')
    
    def pop(self, index=-1):
        pass
    
    def clear(self):
        if self.is_empty():
            return
        del_item = self.head
        self.head = None
        del del_item
    
    def union(self, obj):
        for i in obj:
            self.append(i)
    
    def sort(self, key=None, reverse=False):
        self.head = LinkNode.link(sorted(self, key=(lambda x: key(x.val)) if key else (lambda x: x.val), reverse=reverse)).head
    
    def resever(self):
        if self.is_empty():
            return
        self.head = self[::-1].head
    
    def count(self, val):
        if self.is_empty():
            return 0
        con = 0
        for i in self.head:
            if i.val == val:
                con += 1
        return con
    
    def copy(self):
        return deepcopy(self)
    
    def list(self):
        return [i.val for i in self]
    
    @staticmethod
    def link(iterable, copy=True):
        temp = LinkNode()
        for i in iterable:
            temp.append(i, copy=copy)
        return temp
